package com.c2b.algorithm.newcoder;

/**
 * <a href='https://www.nowcoder.com/practice/9f3231a991af4f55b95579b44b7a01ba?tpId=295&tqId=23269&ru=%2Fpractice%2F96bd6684e04a44eb80e6a68efc0ec6c5&qru=%2Fta%2Fformat-top101%2Fquestion-ranking&sourceUrl=%2Fexam%2Foj'>BM21 旋转数组的最小数字 </a>
 *
 * @author c2b
 * @since 2024/3/14 13:54
 */
public class BM21MinNumberInRotateArray {
    public static class Solution {
        /**
         * 1.如果mid > right，说明mid-right之间存在被旋转数组，left = mid+1。
         * 2.如果mid < right,说明mid右侧整体有序，最小的一定在mid（包含）及其左边
         * 3.如果mid=right，无法判断，只能缩小范围right--；
         */
        public int minNumberInRotateArray(int[] array) {
            int leftIndex = 0;
            int rightIndex = array.length - 1;
            int midIndex;
            while (leftIndex < rightIndex) {
                midIndex = leftIndex + ((rightIndex - leftIndex) >> 1);
                if (array[midIndex] < array[rightIndex]) {
                    rightIndex = midIndex;
                } else if (array[midIndex] > array[rightIndex]) {
                    // 右侧是递增状态。最小值在midIndex位置或者其右侧
                    leftIndex = midIndex + 1;
                } else {
                    rightIndex--;
                }
            }
            return array[leftIndex];
        }
    }
}
